package com.ljy.my_study.lintcode.最大子数组;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * @author James
 * @date 2018年10月16日
 */
public class TestMain {
	// 描述
	// 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
	//
	// 子数组最少包含一个数
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
	//
	// 挑战
	// 要求时间复杂度为O(n)
	public static void main(String[] args) {
		// System.out.println(maxSubArray(new int[] {-2,2,-3,4,-1,2,1,-5,3,7}));
		System.out.println(myMaxSubArray(new int[] { 37, 90, 40, 73, 80, 12, 84, -2, 43, 82, 31, 91, -32, -5, 23, 48, 37,
				-32, 42, 42, 12, 59, 46, 99, 30, 3, -39, 31, 48, 26, -1, -22, 49, 20, -1, 72, 92, 70, -26, 8, 29, 11,
				-39, 92, 25, 80, 78, 5, -46, -28, 35, -15, -26, 9, 1, -23, 55, 94, 47, 6, 57, 67, 93, -12, 87, 47, -12,
				-29, -7, -48, 2, 11, 46, 1, -50, 59, 39, -38, 28, 97, 60, 0, 29, 75, 71, 57, 15, 66, 1, 8, -22, 23, 19,
				35, 48, 50, 95, 59 }));
		System.out.println("-----------------------");
		System.out.println(maxSubArray(new int[] { 37, 90, 40, 73, 80, 12, 84, -2, 43, 82, 31, 91, -32, -5, 23, 48, 37,
				-32, 42, 42, 12, 59, 46, 99, 30, 3, -39, 31, 48, 26, -1, -22, 49, 20, -1, 72, 92, 70, -26, 8, 29, 11,
				-39, 92, 25, 80, 78, 5, -46, -28, 35, -15, -26, 9, 1, -23, 55, 94, 47, 6, 57, 67, 93, -12, 87, 47, -12,
				-29, -7, -48, 2, 11, 46, 1, -50, 59, 39, -38, 28, 97, 60, 0, 29, 75, 71, 57, 15, 66, 1, 8, -22, 23, 19,
				35, 48, 50, 95, 59 }));
		
	}

	public static int myMaxSubArray(int[] array) {
		int arrLen=array.length;
		int[][] arrays=new int[arrLen+1][arrLen+1];
		int sum=0;
		int[] end= {0,0};
		for(int i=0;i<arrLen;i++) {
			arrays[0][i]=array[i];
			if(sum<array[i]) {
				sum=array[i];
				end[1]=i;
			}
		}
		for(int i=1;i<arrLen+1;i++) {
			for(int j=1;j<arrLen+1;j++) {
				arrays[i][j]=arrays[i-1][j-1]+arrays[0][j];
				if(sum<arrays[i][j]) {
					sum=arrays[i][j];
					end[0]=i;
					end[1]=j;
				}
			}
		}
		System.out.println("sum:"+sum);
		System.out.println("len:"+end[0]+",start:"+(end[1]-1)+",end:"+end[1]);
		System.out.println("----------------------");
		for(int i=0;i<arrLen+1;i++) {
			for(int j=0;j<arrLen+1;j++) {
				System.out.print(arrays[i][j]+"	");
			}
			System.out.println();
		}
		
		return sum;
	}
	
	public static int maxSubArray(int[] nums) {
		int len = nums.length;
		Integer maxSum = null;
		int[][] sumArr = new int[len][len + 1];
		sumArr[0][0] = 0;
		for (int i = 0; i < len; i++) {
			for (int j = 1; j <= len; j++) {
				if (i + j > len)
					break;
				sumArr[i][j] = sumArr[i][j - 1] + nums[i + j - 1];
				if (maxSum == null || maxSum < sumArr[i][j]) {
					maxSum = sumArr[i][j];
				}
			}
		}
		return maxSum;
	}

	public static int max(int m, int n) {
		return m > n ? m : n;
	}

	public static int maxSubArray2(int[] a) {
		int nAll = a[0];// 有n个数字数组的最大子数组之和
		int nEnd = a[0];// 有n个数字数组包含最后一个元素的子数组的最大和
		for (int i = 1; i < a.length; i++) {
			nEnd = max(nEnd + a[i], a[i]);
			nAll = max(nEnd, nAll);
		}
		return nAll;
	}


	/**
	 * 求出最大子数组的开始begin，结尾end，以及整个子数组
	 */
	public static int maxSubArray3(int[] a) {
		int begin = 0;
		int end = 0;
		int maxSum = Integer.MIN_VALUE;
		int nSum = 0;
		int nStart = 0;
		for (int i = 0; i < a.length; i++) {
			if (nSum < 0) {
				nSum = a[i];
				nStart = i;
			} else {
				nSum += a[i];
			}
			if (nSum > maxSum) {
				maxSum = nSum;
				begin = nStart;
				end = i;
			}
		}
		return maxSum;
	}
}
